package leetcode;

/*
447. 回旋镖的数量
给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
示例:
输入:
[[0,0],[1,0],[2,0]]
输出:
2
解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
*/

import java.util.HashMap;
import java.util.Map;

public class problems_447 {
    public static void main(String[] arge) {
        System.out.println(new Solution().numberOfBoomerangs(new int[][]{
                {0, 0},
                {1, 0},
                {-1, 0},
                {0, 1},
                {0, -1}
        }));
    }

    static class Solution {
        public int numberOfBoomerangs(int[][] points) {
            int sum = 0;
            int n = points.length;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    int x1 = points[i][0];
                    int y1 = points[i][1];
                    int x2 = points[j][0];
                    int y2 = points[j][1];
                    int dis = (int) (Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2));
                    if (map.containsKey(dis)) {
                        int times = map.get(dis);
                        sum += 2 * times;
                        map.put(dis, times + 1);
                    } else {
                        map.put(dis, 1);
                    }
                }
                map.clear();
            }
            return sum;
        }
    }


//    static class Solution {
//        // 题目解析，就是说，输入N个点，要求找出三个点，是一条直线，且中间点是中位数的情况
//        public int numberOfBoomerangs(int[][] points) {
//            int ret = 0;
//            for (int i = 0; i < points.length - 2; i++) {
//                for (int j = i + 1; j < points.length - 1; j++) {
//                    for (int k = j + 1; k < points.length; k++) {
//                        // 取得三点，符合规则(中位数时，A+C=2B，A+B+C=3B)
//                        int[] pointA = points[i];
//                        int[] pointB = points[j];
//                        int[] pointC = points[k];
//                        //
//                        int[] x = new int[]{pointA[0], pointB[0], pointC[0]};
//                        int[] y = new int[]{pointA[1], pointB[1], pointC[1]};
//                        Arrays.sort(x);
//                        Arrays.sort(y);
//                        if ((x[0] + x[2] == x[1] * 2) && (y[0] + y[2] == y[1] * 2)){
//                            System.out.print("[" + pointA[0] + "," + pointA[1] + "]");
//                            System.out.print("[" + pointB[0] + "," + pointB[1] + "]");
//                            System.out.print("[" + pointC[0] + "," + pointC[1] + "]");
//                            System.out.println();
//                            ret += 2;
//                        }
//                    }
//                }
//            }
//            return ret;
//        }
//    }
}